package com.ma.dp.subsequence;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @ClassName Solution354
 * @Author: mayongqiang
 * @DATE 2022/4/7 14:05
 * @Description: 俄罗斯套娃信封问题
 */
public class Solution354 {
    public static void main(String[] args) {
        /*输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
          输出：3
          解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。*/
        int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
        System.out.println(maxEnvelopes01(envelopes));

    }

    public static int maxEnvelopes01(int[][] envelopes) {
        int n = envelopes.length;
        Arrays.sort(envelopes, (a, b) -> b[0] - a[0]);
        int[] dp = new int[n];
        int res = 0;
        for (int i = 0; i < n; i++) {
            int maxH = 0;
            for (int j = 0; j < i; j++) {
                if (envelopes[j][0] > envelopes[i][0] && envelopes[j][1] > envelopes[i][1]) {
                    maxH = Math.max(dp[j], maxH);
                }
            }
            dp[i] = maxH + 1;
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public static int maxEnvelopes(int[][] envelopes) {
        if (envelopes.length == 0) {
            return 0;
        }
        int n = envelopes.length;
        // 信封按长度递增，相同长度的信封把宽度最大的放前面
        Arrays.sort(envelopes, (a, b) ->
                a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }
}
